package _0528_Random_Pick_with_Weight;

/**
 * Date: 2021/8/30 11:18
 * 执行用时：23 ms, 在所有 Java 提交中击败了99.11%的用户
 * 内存消耗：43.6 MB, 在所有 Java 提交中击败了14.67%的用户
 */
public class Solution {

    int[] s;
    int t;  // 数组总和

    public Solution(int[] w) {
        s = w;
        for (int i = 1; i < w.length; i++) s[i] += s[i - 1];
        t = s[s.length - 1];
    }

    public int pickIndex() {
        int x = (int) (Math.random() * t) + 1;
        int l = 0, r = s.length - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (s[mid] >= x) r = mid;
            else l = mid + 1;
        }
        return r;
    }

    public static void main(String[] args) {

        Solution t = new Solution(new int[]{1, 2, 3});
        for (int i = 0; i < 100; i++)
            System.out.println(t.pickIndex());
    }
}
